[BAEKJOON] 1253. 좋다

Posted on April 27, 2021

문제 :

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입력 :

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

출력 :

좋은 수의 개수를 첫 번째 줄에 출력한다.

풀이 :

최근 코테에서.. 투포인터에 크게 당했기에.. 투 포인터의 유형을 조금은 확실하게 가다듬고 가기 위해 최대한 투포인터 기본 유형부터 살펴보았다.

본 문제의 경우 사실 투 포인터의 개념을 사용해야 된다는 것만 알면 구현하기 쉬운 문제이다.

본 문제는 특정 숫자가 다른 숫자 두개의 합으로 표현할 수 있는지 판별하는 것인데, 모든 숫자들을 오름차순으로 정렬한 후 왼쪽 border, 오른쪽 border을 두고 양쪽 border의 합이 현재 찾으려는 숫자보다 클 경우는 right border을 한칸 줄이고 값이 더 작을 경우에는 left border을 한칸 늘리는 식으로 구현하면 쉽게 해결이 가능하다.

코드 :

코드 보기/접기

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
vector<int> inputvec;
int n;

bool isGoodNumber(int curidx) {
    int leftidx = 0, rightidx = n - 1, comparenum = inputvec[curidx];

    while (1) {
        if (leftidx == curidx) leftidx++;
        if (rightidx == curidx) rightidx--;
        if (leftidx >= rightidx) break;

        int bordersum = inputvec[leftidx] + inputvec[rightidx];
        if (bordersum == comparenum) return true;
        if (bordersum < comparenum) leftidx++;
        else rightidx--;
    }
    return false;
}

int main() {
    int input, goodnumcount = 0;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> input;
        inputvec.push_back(input);
    }

    sort(inputvec.begin(), inputvec.end());

    for (int i = 0; i < n; i++)
        if (isGoodNumber(i)) goodnumcount++;
    cout << goodnumcount << '\n';
    return 0;
}

Algorithm

algorithm baekjoon C++